package algorithms.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.logging.Logger;

/**
 * 插入排序<br>
 *
 * <br>算法思想：<br>
 * 1 类比人们整理桥牌的方法，将每一张牌插入到其他已经有序到牌中的适当位置。<br>
 * 2 与选择排序相同的是，当前索引左边到元素都是有序，不同的是，他们的最终位置还不确定。<br>
 *
 * <br>特点：<br>
 * 插入排序的时间与输入元素的初始顺序有关。例如（按照升序），对一个很大且其中的元素已经基本有序的数组进行排序会比随
 * 机或是逆序的数组进行排序要快得多<br>
 *
 */
public class InsertionSort {

    private static Logger logger = Logger.getLogger(InsertionSort.class.getPackage().getName());


	public static void sort(Comparable[] a){
		int N = a.length;
		for(int i = 1; i < N; i++){
			for(int j = i; j > 0 && less(a[j], a[j - 1]); j--){
				exch(a, j, j - 1);
			}
		}
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	
	public static void show(Comparable[] a){
        if(a == null)   return;
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
            logger.info("插入排序Demo");
			String s = br.readLine();
			String[] in = s.split(" ");
            InsertionSort.sort(in);
			InsertionSort.show(in);
		} catch (IOException e) {
			e.printStackTrace();
		}

	}


}
